In computer graphics, circle and ellipse generation is an operation as fundamental as line drawing and point plotting. In the prior art, several methods have been developed to generate a circle, and the more general form of an ellipse. These methods generally employ a sequence of steps that involve plotting a pixel at a known starting point, and repeatedly plotting contiguous pixels by moving in the X and Y directions.
An important goal for drawing methods is to keep execution speed as high as possible. For this reason, most circle generation methods use simple arithmetic, such as addition and comparison, in the drawing loop. Operations such as multiplication and division are avoided, since complex operations in the drawing loop affect the execution speed significantly. Another design decision is to use integer numbers in the drawing loop, because integer manipulation is simpler and faster than floating-point manipulation.
A review of the prior art begins with a circle drawing method described by J. Bresenham. The Digital Differential Analyzer (DDA), also known as Bresenham's algorithm, is described in "Dr. Dobbs Joumal", July 1994, pages 119-120. The DDA employs a high-speed drawing loop in which calculations are restricted to integer addition and integer comparison. The DDA is very fast, but is limited in scope. The DDA can only generate ellipses that have their major and minor axes fixed squarely on the X and Y axes, and can only draw ellipses in two dimensions. Furthermore, the DDA is designed to paint the ellipse in one color only. No provision is made to texture the ellipse.
A system for generating a circular or elliptic arc is given in U.S. Pat. No. 5,146,551 to Atsushi Miyazawa (Sep. 8, 1992). This system employs a modified DDA specifically designed to calculate the scan-line intersection points for an ellipse. The basic improvement over the DDA is the ability to forecast the length of straight line segments that compose the ellipse.
A method for generating an ellipse is provided by U.S. Pat. No. 4,941,116 to William R. Hancock et al (Jul. 10, 1990). This method provides a major improvement in ellipse drawing in that an ellipse can be drawn with any orientation in space. However this method does not provide the ability to draw an ellipse in perspective. This method also suffers from the requirement of multiplication's in the drawing loop. The drawing method uses a sin and cos look-up table. The X and Y coordinates are generated by combining an X and a Y circle, each circle having a different radius and starting angle. The two circles are rotated together with a common angular increment. The X and Y coordinates are simply found by using the rotation angle of each circle as an index into the cos or sin table, and extending the resultant position by radius of each circle. In analyzing the drawing loop, note that the two multiplications required to find each point add significant complexity to the ellipse generation. In addition, the angular increment that directs the rotation of the two circle has to be chosen carefully. If the circles are rotated too far between successive points, the ellipse may show a gap. Therefor, the angular increment is chosen to be small to provide a continues curve. This decision may result in some points being over-written multiple times, as the rotation increment does not always carry the circles to a new point. This drawing method is implemented as a dedicated digital circuit, with hardware multipliers. The required multiplications in the drawing loop will cause a significant execution slowdown on a computer CPU. Note that this drawing method can provide texture information to the ellipse on the screen, by using the rotation angle to lookup a color. This effectively maps color onto the ellipse as a function of rotation angle.
The prior art methods described thus far are designed to generate an ellipse in two dimensions. Although drawing an ellipse with true perspective is a desirable goal in computer graphics, the present state of the art does not provide an efficient method for doing so. One conceivable method of drawing an ellipse with perspective is to use the perspective formula to translate an ellipse generated in world space to a curve on the display screen. The perspective formula is given as: EQU screen x=space.x/space.z EQU screen.y=space.y/space.z
The points of an ellipse are found in world space: X, Y and Z dimensions. Each space point is then translated using the perspective formula to a screen point. This method does generate a perspective ellipse, but suffers from the requirement of two divisions per pixel. To this date, a method to avoid these divisions has not yet been discovered.
An additional problem that arises in translating world space points to perspective screen points is the possibility of gaps between successive screen points. Consider, for instance, what happens when the Z coordinate of a curve grows smaller.
This occurs in the section of the ellipse that is closest to the viewer. Here, the apparent size of the curve expands. As a result, the perspective formula may produce a curve with gaps between the neighboring screen points. These gaps can be avoided by refining the ellipse drawn in world space. But then screen points may well be over-written numerous times before moving on to a new screen point. This method, which cannot avoid superfluous calculations, can only be characterized as inefficient (especially when considering that the calculations are division operations).
For this reason, the prior art simulates perspective curves by a series of short chained straight vectors that gradually change orientation to approximate curvature. The straight-line method calculates the intermediary points along the curve, computes the perspective locations of these points, and generates the straight line segments to complete the curve. However, when the number of segments is not large enough, the distortion in the curve becomes noticeable. Therefore many short line vectors must be used if a really smooth curve is desired. This increases the time cost of drawing the curve. In addition, providing color texture along each straight-line segment requires the application of a parabolic approximation to simulate the depth change of perspective. Computing the parabolic formula burdens this method even more. As a result, textured ellipses drawn in perspective have been relatively complex to implement in computer graphics.
A high-speed method for drawing elliptical curves, in both two and three dimensions with perspective, with color texture and (optional) anti-aliasing, is a desirable tool to complement the existing state-of-art in computer graphics. Such a method, if simple enough, can be performed by a dedicated digital circuit to provide the highest possible drawing speed. Such a method can be used to construct a wide variety of curved lines by fitting together different sections of elliptical arcs. And, such a method may provide the ability to construct solid-looking rounded shapes, such as spheres, by combining several elliptical curves lying next to each other.